package demo.DataStrucAndAlgo.Easy_pritice;

import java.util.*;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/9/8-09-08-19:07
 * @Description：demo.DataStrucAndAlgo.Easy_pritice
 */
public class sum_any {
    public static void main(String[] args) {
        int[] num = {10,1,2,7,6,1,5};
        System.out.println(combinationSum(num, 8));
    }
    static List<List<Integer>> result = new ArrayList();
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        if(target < candidates[0]){
            return null;
        }
        dfs(candidates,0,target);
//        for(int i = 0; i< candidates.length && candidates[i] < target; i++){
//            if(i > 0 && candidates[i] == candidates[i-1] || candidates[i] > target){
//                continue;
//            }
//            temp.add(candidates[i]);
//            dfs(candidates,i,target-candidates[i]);
//            temp.pop();
//        }

        return result;
    }
    static Stack<Integer> temp = new Stack<>();
    public static void dfs(int[] candidates, int begin,int target){
        if(target == 0){
            result.add(new ArrayList<>(temp));
            //temp = new Stack<>();
            return;
        }else{
            for(int i = begin; i < candidates.length; i++){
                if( candidates[i] > target){
                    break;
                }
                if(i > begin && candidates[i] == candidates[i-1]){
                    continue;
                }
                temp.add(candidates[i]);
                dfs(candidates,i+1,target-candidates[i]);
                temp.pop();
            }

        }
    }
}
